package com.lisp.algorithm.tree;

import com.lisp.algorithm.util.Assert;
import com.lisp.algorithm.util.SortUtil;

public class BinarySearchTree {

    public static void main(String[] args) {
        SortUtil.test(BinarySearchTree::sort1);
        SortUtil.test(BinarySearchTree::sort2);
        SortUtil.test(BinarySearchTree::sort3);
        SortUtil.test(BinarySearchTree::sort4);
        SortUtil.test(BinarySearchTree::sort5);
    }
    
    private Node root;
    
    public BinarySearchTree(int a[]) {
        for(int x : a) {
            insert(x);
        }
    }
    
    public static void sort1(int a[]) {
        BinarySearchTree bst = new BinarySearchTree(a);
        bst.inorder(a);
    }
    
    public static void sort2(int a[]) {
        BinarySearchTree bst = new BinarySearchTree(a);
        for(int i=0; i<a.length; i++) {
            Node min = bst.min(bst.root);
            bst.delete(min.key);
            a[i] = min.key;
        }
    }
    
    public static void sort3(int a[]) {
        BinarySearchTree bst = new BinarySearchTree(a);
        for(int i=a.length-1; i>=0; i--) {
            Node max = bst.max(bst.root);
            bst.delete(max.key);
            a[i] = max.key;
        }
    }
    
    public static void sort4(int a[]) {
        BinarySearchTree bst = new BinarySearchTree(a);
        Node max = bst.max(bst.root);
        a[a.length-1] = max.key;
        
        for(int i=a.length-2; i>=0; i--) {
            Node predecessor = bst.predecessor(max);
            bst.deleteExactly(max);
            
            max = predecessor;
            a[i] = predecessor.key;
        }
    }
    
    public static void sort5(int a[]) {
        BinarySearchTree bst = new BinarySearchTree(a);
        Node min = bst.min(bst.root);
        a[0] = min.key;
        
        for(int i=1; i<a.length; i++) {
            Node successor = bst.successor(min);
            bst.deleteExactly(min);
            
            min = successor;
            a[i] = successor.key;
        }
    }
    
    public void inorder(int a[]) {
        inorder(root, a, 0);
    }
    
    private int inorder(Node start, int a[], int idx) {
        if(start == null) {
            return idx;
        }
        idx = inorder(start.left, a, idx);
        a[idx++] = start.key;
        return inorder(start.right, a, idx);
    }
    
    public Node search(int k, Node start) {
        if(start == null) {
            return null;
        }
        
        if(start.key == k) {
            return start;
        } else if(start.key < k) {
            return search(k, start.right);
        } else {
            return search(k, start.left);
        }
    }
    
    public Node search(int k) {
        return searchLoop(k, root);
    }
    
    public Node searchLoop(int k, Node start) {
        while(true) {
            if(start == null || start.key == k) {
                return start;
            } else if(start.key < k) {
                start = start.right;
            } else {
                start = start.left;
            }
        }
    }
    
    public Node max(Node start) {
        if(start == null) {
            return null;
        }
        
        Node ret = start;
        while(ret.right != null) {
            ret = ret.right;
        }
        return ret;
    }
    
    public Node min(Node start) {
        if(start == null) {
            return null;
        }
        
        Node ret = start;
        while(ret.left != null) {
            ret = ret.left;
        }
        return ret;
    }
    
    public Node successor(Node start) {
        Assert.isTrue(start != null);
        
        if(start.right != null) {
            return min(start.right);
        } else {
            Node parent = start.parent;
            Node left = start;
            while(parent != null && parent.left != left) {
                left = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
    
    public Node predecessor(Node start) {
        Assert.isTrue(start != null);
        
        if(start.left != null) {
            return max(start.left);
        } else {
            Node parent = start.parent;
            Node right = start;
            while(parent != null && parent.right != right) {
                right = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
    
    public void insert(int key) {
        if(root == null) {
            root = new Node(key, null);
        } else {            
            insert(key, root);
        }
    }
    
    public void insert(int key, Node start) {
        
        Assert.isTrue(start != null);
        
        Node p = start;
        Node nil = p;
        while(nil != null) {
            if(key > nil.key) {
                p = nil;
                nil = nil.right;
            } else {
                p = nil;
                nil = nil.left;
            }
        }
        
        Node newNode = new Node(key, p);
        if(key > p.key) {
            p.right = newNode;
        } else {
            p.left = newNode;
        }
    }
    
    public void delete(int key) {
        delete(key, root);
    }
    
    public void delete(int key, Node start) {
        Assert.isTrue(start != null);
        
        Node delete = search(key, start);
        if(delete == null) {
            return;
        }
        deleteExactly(delete);
    }
    
    public void deleteExactly(Node delete) {
        if(delete.left == null) {
            transplant(delete, delete.right);
        } else if(delete.right == null) {
            transplant(delete, delete.left);
        } else {
            Node successor = successor(delete);
            
            // successor必定位于delete的右子树，且successor.left必定为null
            deleteExactly(successor);
            
            delete.key = successor.key;
        }
    }
    
    private void transplant(Node u, Node v) {
        if(u.parent == null) {
            root = v;
        } else if(u.parent.left == u) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        
        if(v != null) {
            v.parent = u.parent;
        }
    }
    
    static class Node {
        int key;
        Node left;
        Node right;
        Node parent;
        
        Node() { }
        
        Node(int key, Node parent) {
            this.key = key;
            this.parent = parent;
        }
        
        public String toString() {
            return String.format("key=%s, left=%s, right=%s, parent=%s", 
                    key, 
                    left == null ? null : left.key,
                    right == null ? null : right.key,
                    parent == null ? null : parent.key);
        }
    }
}
